package cn.edu.njust.alg.leetcode;

/**
 * 创建时间：2015年6月15日 上午11:47:37 项目名称：AlgorithmExercise
 * 
 * @author Zhou Xiumin
 * @version 1.0
 * @since JDK 1.7.0_21 文件名称：Leetcode_0_t.java 类说明：
 */
public class Leetcode_96_Unique_Binary_Search_Trees {
	public static int gcd(int a, int b) {
		if (b == 0) {
			return a;
		} else {
			return gcd(b, a % b);
		}
	}

	public static int numTrees(int n) {
		int h = 1;
		for (int i = 1; i <= n; i++) {
			int p = 4 * i - 2;
			int g = gcd(p, i + 1);
			h = (p / g) * (h / ((i + 1) / g));
			
		}
		return h;
	}

	public static void main(String[] args) {
		System.out.println(numTrees(19));
	}

}
